This invention relates to digital communications and more specifically to techniques for constructing bandwidth efficient signal sets by combining error correcting encoding with modulation of digital data. More specifically, the invention relates to generalized methods and apparatus for encoding and modulating digital information signals and methods and apparatus for demodulating and decoding signals from an information channel containing information. The invention finds particular application to time-division multiple-access (TDMA) operation in a frequency-division multiple-access environment, such as a satellite transponder channel.
In order to aid in identifying the relevance of the references cited herein, the references cited herein are referred to frequently by the abbreviations following the citations listed hereinbelow.
In electronic data communication systems, random noise or interference can cause the transmitted signal to be contaminated and lead to errors in the received message. In systems where the reliability of received data is very important, error-correcting codes have been used to protect the transmitted message and enable system designers to reduce the effects of noise. Two major schools of thought and associated bodies of theory have emerged for performing this task: algebraic block coding, which relies heavily on the use of modern algebra and typically constructs codes as linear subspaces of a fixed size vector space over a finite field: and convolutional coding, in which the transmission is viewed as being continuous and the design typically relies more on computer search techniques and close analysis of the state diagram of the possible convolutional encoder circuits.
For many years, the coding process was effectively separated from the problem of modulation in conventional systems. Modulation is the creation of, for example, electromagnetic signals in which changes in phase, frequency, or amplitude are used to distinguish different messages.
Referring to FIG. 1 representing a prior art system 10, in conventional systems 10 a block or stream of information digits 12 is fed into a digital encoder 14 designed for a specific error-correcting code where redundant check bits are added. The resultant encoded digits 16 are then fed into a modulator 18 where each digit or set of digits is typically mapped to a modulated symbol to be transmitted as information in for example a radio frequency signal 20. The radio frequency signal 20 is applied to a channel 22 wherein noise and interference 24 are added and then received as a signal with errors 26 at a demodulator 28. The demodulator 28 attempts to extract from the signal with errors 26 redundant digits with errors 30 which are fed to an error correcting decoder 32 designed to accommodate the error correcting code. The decoder 28 then uses known redundancy structure of in the encoded digits 16 to eliminate as many errors as possible producing as its output estimated received digits 34. In some systems, the demodulator 28 also provides "soft decision information" or "reliability" information along with the estimate of the received digits which can be used effectively in a variety of error-correcting decoders to improve performance, particularly Viterbi decoders for convolutional codes.
To maintain the separations between different messages guaranteed by the minimum Hamming distance of the error-correcting code, the mapping performed by the demodulator 28 must be chosen with care. (The Hamming distance between two words is the number of digits in which the two words differ. The minimum Hamming distance of a code is the minimum over all pairs of code words in the code of the Hamming distance between the two code words.) For example, in binary systems using phase-shift modulations, the correspondence between the redundant binary sequences and the particular phase of a transmitted signal is often dictated by a Gray code.
The use of error-correcting coding in this manner frequently is an alternative to increasing the power of the transmitted signal to overcome the noise. Conversely, the use of coding permits the power of the transmission to be reduced with no degradation in the reliability of the transmission. The power savings obtained in this way are measured in terms of the allowable reduction in decibels of power-per-bit for the same bit error rate, a quantity referred to as "coding gain." However, since coding requires the addition of redundant digits, for a fixed modulation scheme the use of coding requires that symbols be sent at a faster rate, thereby increasing the frequency bandwidth occupied by the transmission.
As the demand for communication links has increased, there has been growing competition for the available electromagnetic spectrum, and significant expansion of the bandwidth of the signal to reduce the power required has no longer been acceptable in many instances. Thus attention has turned to methods of combining coding and modulation into one coordinated mapping to achieve signals that are efficient in both power and bandwidth utilization. In the past, efforts have followed the two pathways set by error-correcting coding theory, with some building on the concepts of convolutional codes whereas others start from the block code ideas.
In the convolutional school, a major step forward was made by Ungerboeck as described in his paper "Channel Coding with Multilevel/Phase Signals" [ung], in which he pointed out that the Euclidean distance properties of the electromagnetic signal space could be incorporated into the design of a convolutional code encoder. FIG. 2 illustrates the basic structure for comparison with FIG. 1. Using the trellis characterization of the encoder, i.e., a trellis encoder 44, information digits 12 are mapped directly to modulated signals 20 so as to add redundancy only when the electromagnetic symbols are likely to be confused. The error-correcting encoder and modulator are combined into a single coder/modulator herein called the trellis encoder 44. The standard Viterbi algorithm for decoding convolutional codes can be readily adapted to a so-called Viterbi trellis decoder 48 to decode the received symbols (signal with errors 26) directly to estimated information digits 34. In adapting the convolutional coding methodology. Ungerboeck chose not to "pursue the block coding aspect because the richer structure and omission of block boundaries together with the availability of Viterbi ML-decoding algorithm [sic] make trellis codes appear to us more attractive for the present coding problem [ung,p.58]."
Others have followed Ungerboeck. For example, recently S. G. Wilson has shown a construction for rate 5/6 trellis codes for an 8-state phase-shift keying (8-PSK) system and has found that it achieves an asymptotic gain of 6.2 dB over an uncoded 8-PSK system [wlsn].
Other researchers have pursued the construction of efficient coding/modulation systems from the algebraic block code point of view. Imai and Hirakawa showed how error-correcting codes of increasing strengths can be coupled to increasingly error-sensitive parameters of the signal modulation in both multilevel and multiphase modulations to give improved performance. Furthermore they explained a staged decoding method in which the most sensitive parameters are estimated first, using the a posteriori probabilities based on the channel statistics and the code structure wherein those estimates are used in later probability calculations to determine estimates for the successively less sensitive parameters [i&h].
Similarly, V. V. Ginzburg has used algebraic techniques to design multilevel multiphase signals for a continuous channel. His methods address the case where the measure of distance in the continuous channel is monotonically related to an additive function of the distances between individual signal components. (Such additivity is commonly assumed in satellite channel models, for example.) He generalized the ideas of Imai and Hirakawa by partitioning the set of elementary modulation signals into carefully chosen subsets that permit the actual channel distance between signals to be associated with the particular subsets in which the signals are found. He then combined a hierarchy of subsets with a matching hierarchy of codes of increasing strength to design signal sets that are guaranteed to have large separations in the signal space. The algorithms he suggested for demodulating and decoding the signals has been given in only abstract mathematical terms: "A rigorous maximum-likelihood demodulation procedure of acceptable complexity may be built only in exceptional cases. A most simple approximate procedure implementing an energy distance D (i.e., one that leads to a correct decision for a noise energy &lt;D/4) may be built as a sequence of integral reception procedures (to be carried out in the order of decreasing levels) for the individual codes that define the signal-system construction, if each of them implements D . . . " [gnz].
Most recently, Sayegh [syh] has developed further the methods of Imai and Hirakawa by explicitly defining particular block codes that can be attached to the various levels of a hierarchy which admits to soft-decision decoding procedures, and he has demonstrated some achievable gains using his methods through simulation studies for very short codes. Sayegh's work is notable as well in that he has shown how Imai and Hirakawa's method can be combined with the signal set partitions of Ungerboeck to create combined coding and modulation systems based on several other signal constellations. Sayegh's work represents what is believed to be the most relevant development to the present invention. However, Sayegh does not represent a prior art publication, since publication was less than one year prior to the filing date of the present application.
Other authors [ck&sl] [frny86] have approached the problem of constructing bandwidth efficient signal sets using mathematically defined lattices. Thus, their work is distinguishable as essentially unrelated to the present scheme.